package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

type intList []int

const ARRAY_LNEGH = 10

func init() {
	rand.Seed(time.Now().UnixNano())
}

func main() {
	for i := 0; i < 1000; i++ {
		arr := createRandomArray(10, 100)
		dup := copySlice(arr)
		//bubbleSort(arr)
		//selectSort(arr)
		insertSort(arr)
		if !isArraySortedRight(dup, arr) {
			printArray(arr)
		}
	}
}

func copySlice(arr intList) intList {
	result := make(intList, len(arr), len(arr))
	copy(result, arr)
	return result
}

// 传入原始Slice的拷贝和排序后的Slice来判断排序是否正确，先判断所有元素是否和原来元素一样，再判断是否排好了序
func isArraySortedRight(dup intList, arr intList) bool {
	sort.Sort(dup)
	if len(dup) != len(arr) {
		return false
	}
	for i := range arr {
		if dup[i] != arr[i] {
			return false
		}
	}
	return isArraySorted(arr)
}

// 创建随机Slice
func createRandomArray(n int, limit int) intList {
	arr := make(intList, n, n)
	for i := 0; i < len(arr); i++ {
		arr[i] = rand.Intn(limit)
	}
	return arr
}

// 打印Slice
func printArray(arr intList) {
	for _, value := range arr {
		fmt.Printf("%d\t", value)
	}
	fmt.Println()
}

// 判断Slice是否从小到大排好序
func isArraySorted(arr intList) bool {
	for i := 0; i < len(arr)-1; i++ {
		if arr[i+1] < arr[i] {
			return false
		}
	}
	return true
}

// 冒泡排序
func bubbleSort(arr intList) {
	for i := range arr {
		for j := len(arr) - 1; j > i; j-- {
			if arr[j-1] > arr[j] {
				arr[j-1], arr[j] = arr[j], arr[j-1]
			}
		}
	}
}

// 选择排序
func selectSort(arr intList) {
	var minIndex int
	for i := range arr {
		minIndex = i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
}

// 插入排序
func insertSort(arr intList) {
	for i := 1; i < len(arr); i++ {
		temp := arr[i]
		j := i
		for j > 0 && arr[j-1] > arr[j] {
			arr[j] = arr[j-1]
			j--
		}
		arr[j] = temp
	}
}

func (l intList) Len() int {
	return len(l)
}

func (l intList) Swap(i, j int) {
	l[i], l[j] = l[j], l[i]
}

func (l intList) Less(i, j int) bool {
	return l[i] < l[j]
}
